package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC875 {

    int minEatingSpeed(int[] piles, int H) {
        int lb = 1, ub = getMax(piles), mid = 1;
        while (lb <= ub) {
            mid = lb + (ub - lb) / 2;//in case of integer overflow
            if (canFinish(piles, mid, H)) {
                ub = mid - 1;
            } else {
                lb = mid + 1;
            }
        }

        return lb;
    }

    // 时间复杂度 O(N)
    boolean canFinish(int[] piles, int speed, int H) {
        int time = 0;
        for (int n : piles) {
            time += timeOf(n, speed);
        }
        return time <= H;
    }

    int timeOf(int n, int speed) {
        return (n / speed) + ((n % speed > 0) ? 1 : 0);
    }

    int getMax(int[] piles) {
        int max = 0;
        for (int n : piles)
            max = Math.max(n, max);
        return max;
    }


    public int getTripleMin(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }

    public static void main(String[] args) {
        LC875 an = new LC875();
        int[] arr = InputUtil.toIntegerArray("  [30,11,23,4,20]");
        System.out.println(an.minEatingSpeed(arr, 5));
    }
}
